package book; // from LC 198

public class CarPlanSolution {

    // 第1种计算最大收益的方法（动态规划，使用数组记录中间状态）
    public int plan1(int[] E) {
        int n = E.length;

        // dp[i]表示从E[0..i]中取得的最大收益
        int[] dp = new int[n];

        for (int i = 0; i < n; ++i) {
            // 分支1：第i天不出行，所以收益为0，总收益跟之前一样
            if (i > 0) // 代码细节：不加这个判断下一句有可能数组越界
                dp[i] = dp[i - 1];

            // 分支2：当天出行，这样E[i-1]就不能出行，总收益加上dp[i-2]
            int money = E[i];
            if (i >= 2) 
                money += dp[i - 2];
            if (money > dp[i]) 
                dp[i] = money; 
        }
        // 备忘录的最后一个值为答案
        return dp[n - 1];
    }

    // 优化：第2种计算最大收益的方法（滚动数组思想）
    public int plan(int[] E) {
        // dp1表示到当天为止的最大收益
        // dp2表示到前一天为止的最大收益
        int dp1 = 0, dp2 = 0;

        for (int x: E) {
            // 缓存滚动后的前一天数据
            int temp = dp1;

            // 计算当天数据，计算方式和之前一样
            dp1 = Math.max(dp1, x + dp2);

            // 还原缓存的数据到dp2
            dp2 = temp;
        }
        // 计算到最后的dp1为最终答案
        return dp1;
    }

    public static void main(String[] args) {
        int[] E = { 7, 9, 7, 1, 6, 8, 3, 4 };
        int result = new CarPlanSolution().plan(E);
        System.out.println("最大收益: " + result);
    }
}
